package C060;

import java.util.List;
import java.util.*;

/**
 * ClassName: c063
 * Package: C060
 * Description:
 * 2050. 并行课程 III
 * https://leetcode.cn/problems/parallel-courses-iii/description/
 * @Author BCXJ
 * @Create 2025/11/27 08:51
 * @Version 1.0
 * @Since 1.0
 */
public class c03 {
    public static void main(String[] args) {
        // n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
        int[][] arr = {{1,7},{1,4},{1,3},{2,3},{4,3},{5,3},{7,3},{7,6}};
        int[] arr2 = {6,5,1,8,2,9,4};
        System.out.println(minimumTime(7, arr, arr2));
    }

    /*
    提示：

    1 <= n <= 5 * 104
    0 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)
    relations[j].length == 2
    1 <= prevCoursej, nextCoursej <= n
    prevCoursej != nextCoursej
    所有的先修课程对 [prevCoursej, nextCoursej] 都是 互不相同 的。
    time.length == n
    1 <= time[i] <= 104
    先修课程图是一个有向无环图。

     */

    static int MAXN = 5 * 10000 + 1;
    static List<List<Integer>> grap = new ArrayList<>();
    static {
        for (int i = 0; i < MAXN; i++) {
            grap.add(new ArrayList<>());
        }
    }

    // 入度表
    static int[] indegree = new int[MAXN];

    // 队列
    static int[] queue = new int[MAXN];
    static int l, r;


    // 节点数 ， 边：0 -> 1, (i + 1)课 花费时间
    public static int minimumTime(int n, int[][] relations, int[] time) {
        // 初始化图
        for (int i = 1; i <= n; i++) {
            grap.get(i).clear();
        }
        Arrays.fill(indegree, 0);
        l  = r = 0;

        // 建图
        for (int i = 0; i < relations.length; i++) {
            grap.get(relations[i][0]).add(relations[i][1]);
            indegree[relations[i][1]]++;
        }

        // 入度表初始化 权重数组初始化
        int[] weights = new int[n + 1]; // 权重数组不需要进行初始化
        for (int i = 1; i <= n; i++) {
            if(indegree[i] == 0) {
                queue[r ++] = i;
            }
        }

        // 拓扑排序
        int ans = 0;
        while(l < r) {
            int cur = queue[l ++];
            weights[cur] += time[cur - 1];
            ans = Math.max(ans, weights[cur]);
            for (int next : grap.get(cur)) {
                weights[next] = Math.max(weights[cur], weights[next]);
                indegree[next]--;
                if(indegree[next] == 0) {
                    queue[r ++] = next;
                }
            }
        }

        return ans;
    }


}
